package linklist;

/**
 * @author "随风Coding"
 * @email 1431471764@qq.com
 * @date 2025/8/14 19:37
 */
public class DeteectCycle {

    /**
     * 检测链表中环的入口节点（Floyd判圈算法）
     *
     * @param head 链表头节点
     * @return 环的入口节点（无环返回 null）
     */
    public static ListNode detect(ListNode head) {
        // 初始化快慢指针（均指向头节点）
        ListNode fast = head;
        ListNode slow = head;

        // 快指针每次走2步，慢指针每次走1步，直到相遇或快指针越界
        while (fast != null && fast.next != null) {
            fast = fast.next.next;  // 快指针移动2步
            slow = slow.next;       // 慢指针移动1步

            // 快慢指针相遇，说明存在环
            if (fast == slow) {
                // 寻找环的入口：头节点到入口的距离 = 相遇点到入口的距离
                ListNode index1 = head;    // 从头节点开始
                ListNode index2 = slow;    // 从相遇点开始
                while (index1 != index2) {
                    index1 = index1.next;  // 头节点指针移动
                    index2 = index2.next;  // 相遇点指针移动
                }
                return index1;  // 返回环的入口节点
            }
        }
        // 快指针越界（无环）
        return null;
    }

    // ------------------------------ 辅助方法 ------------------------------

    /**
     * 创建带环的链表（支持无环场景）
     *
     * @param nums       链表节点值数组
     * @param cycleIndex 环入口节点的索引（-1表示无环，0~nums.length-1表示对应位置的节点）
     * @return 带环或不带环的链表头节点
     */
    private static ListNode createListWithCycle(int[] nums, int cycleIndex) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        // 创建虚拟头节点简化操作
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        // 保存所有节点的引用（用于后续设置环）
        ListNode[] nodes = new ListNode[nums.length];

        // 构建基础链表
        for (int i = 0; i < nums.length; i++) {
            current.next = new ListNode(nums[i]);
            current = current.next;
            nodes[i] = current;  // 保存当前节点引用
        }

        // 设置环（cycleIndex=-1时不设置环）
        if (cycleIndex >= 0 && cycleIndex < nums.length) {
            current.next = nodes[cycleIndex];  // 最后一个节点指向环入口
        }
        return dummy.next;  // 返回真实头节点
    }

    // ------------------------------ 测试方法 ------------------------------
    public static void main(String[] args) {
        // 测试用例1：无环链表（cycleIndex=-1）
        ListNode head1 = createListWithCycle(new int[]{1, 2, 3, 4, 5}, -1);
        ListNode result1 = detect(head1);
        printTestResult("测试用例1（无环链表）", result1, null);

        // 测试用例2：有环链表（环入口是中间节点3，索引2）
        ListNode head2 = createListWithCycle(new int[]{1, 2, 3, 4, 5}, 2);
        ListNode result2 = detect(head2);
        printTestResult("测试用例2（环入口3）", result2, new ListNode(3));

        // 测试用例3：整个链表成环（入口是头节点1，索引0）
        ListNode head3 = createListWithCycle(new int[]{1, 2, 3, 4, 5}, 0);
        ListNode result3 = detect(head3);
        printTestResult("测试用例3（全链表成环）", result3, new ListNode(1));

        // 测试用例4：单节点自环（入口是自己，索引0）
        ListNode head4 = createListWithCycle(new int[]{1}, 0);
        ListNode result4 = detect(head4);
        printTestResult("测试用例4（单节点自环）", result4, new ListNode(1));

        // 测试用例5：环在尾部（入口是尾节点2，索引1）
        ListNode head5 = createListWithCycle(new int[]{1, 2}, 1);
        ListNode result5 = detect(head5);
        printTestResult("测试用例5（环入口2）", result5, new ListNode(2));
    }

    /**
     * 辅助方法：打印测试结果
     */
    private static void printTestResult(String testName, ListNode actual, ListNode expected) {
        System.out.print(testName + ": ");
        if (actual == null && expected == null) {
            System.out.println("通过（无环）");
        } else if (actual != null && expected != null && actual.val == expected.val) {
            System.out.println("通过（入口值：" + actual.val + "）");
        } else {
            System.out.println("失败！实际：" + (actual != null ? actual.val : "null") +
                    "，预期：" + (expected != null ? expected.val : "null"));
        }
    }

}